Conversão de Pós-Fixa para Pré-Fixa

Objetivo

Seu objetivo é converter uma expressão pós-fixa (Notação Polonesa Reversa) em sua equivalente expressão pré-fixa (Notação Polonesa) construindo e percorrendo uma árvore de expressão.

Algoritmo

1. Construa a Árvore de Expressão: Processar a expressão pós-fixa da esquerda para a direita usando uma pilha.
   • Quando um operando (por exemplo, A, B) for encontrado, crie uma árvore com um único nó para ele e empilhe-a.
   • Quando um operador (por exemplo, +, *) é encontrado, retire duas árvores da pilha. A primeira retirada é a subárvore direita (T₂) e a segunda é a subárvore esquerda (T₁). Crie uma nova árvore com o operador como raiz e empilhe-a novamente.
2. Gere a String Pré-Fixa: Após processar todos os tokens, a pilha conterá a árvore completa da expressão. Realize uma travessia em pré-ordem (Raiz → Esquerda → Direita) nesta árvore para produzir a expressão pré-fixa final.

Exemplo

Para a expressão pós-fixa A B + C *, o algoritmo constrói a seguinte árvore:

  *
   / \
  +   C
 / \
A   B

Uma travessia em pré-ordem resulta na expressão pré-fixa: * + A B C.

Formato de Entrada/Saída

Entrada

• Linha 1: Um inteiro N (1 ≤ N ≤ 1000), o número de tokens.
• Linha 2: A expressão pós-fixa, com N tokens separados por espaços.

Regras dos Tokens

• Operandos: Letras maiúsculas únicas (A-Z).
• Operadores: Os quatro operadores binários: +, -, *, /.

Saída

• Uma única linha contendo a expressão pré-fixa correspondente, com tokens separados por espaços.

Exemplos

Exemplo 1:

5

A B + C *

* + A B C

Exemplo 2:

7

A B C * + D /

/ + A * B C D

Exemplo 3:

7

A B + C D - *

* + A B - C D

Limitações